package Offer.T36;

/*
    题目:
        输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
        要求不能创建任何新的节点，只能调整树中节点指针的指向。

    思路:
        因为给定的是二叉搜索树，可以采用中序遍历访问结点
        要记录前后结点的关系，可以采用双指针
* */
public class T36_treeToDoublyList {
    Node pre, head;  //用来指向中序遍历当前结点的前驱和头结点

    public Node treeToDoublyList(Node root) {
        inorder(root);  //中序遍历完成后,pre指向最后一个结点
        head.left = pre;
        pre.right = head;
        return head;
    }

    public void inorder(Node cur) {
        if (cur == null) {
            return;
        }
        inorder(cur.left);
        if (pre != null) {
            pre.right = cur;
            cur.left = pre;
        }else {
            head = cur; //当pre为null时，说明cur为头结点
        }
        pre = cur;      //更新pre指针
        inorder(cur.right);
    }

/*
        if (pre != null) {
            pre.right = cur;
        }else {
            head = cur; //当pre为null时，说明cur为头结点
        }
        cur.left = pre; //其实这里pre如果为null也没关系，因为在treeToDoublyList中会修改第一个结点的left；只是这样可读性差一点
        pre = cur;
        inorder(cur.right);
*/

}


class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};